InforLorV4, Main, Exploration, bibRecord, 00A999

Factorization of RSA-140 Using the Number Field Sieve

Identifieur interne : 00A999 ( Main/Exploration ); précédent : 00A998; suivant : 00AA00

Factorization of RSA-140 Using the Number Field Sieve

Auteurs : Stefania Cavallar [Pays-Bas] ; Bruce Dodson [États-Unis] ; Arjen Lenstra [États-Unis] ; Paul Leyland [Royaume-Uni] ; Walter Lioen [Pays-Bas] ; Peter L. Montgomery [États-Unis, Pays-Bas] ; Brian Murphy [Australie] ; Herman Te Riele [Pays-Bas] ; Paul Zimmermann [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:B4A2079E6539944CEB1347B1ADB16FADDBCE4758

Descripteurs français

Pascal (Inist)
- Cryptage, Cryptographie, Factorisation, Implémentation, Internet, Méthode polynomiale, Problème sélection, RSA-140, Réseau WWW, Temps calcul, Théorie nombre.
Wicri :
- topic : Cryptographie.

English descriptors

KwdEn :
- Computation time, Cryptography, Encryption, Factorization, Implementation, Internet, Number theory, Polynomial method, Selection problem, World wide web.

Abstract

Abstract: On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper. The implications of the new polynomial selection method for factoring a 512-bit RSA modulus are discussed and it is concluded that 512-bit (= 155-digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.

Url:

https://api.istex.fr/ark:/67375/HCB-36VVVKXJ-J/fulltext.pdf

DOI: 10.1007/978-3-540-48000-6_16

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Factorization of RSA-140 Using the Number Field Sieve</title>
<author><name sortKey="Cavallar, Stefania" sort="Cavallar, Stefania" uniqKey="Cavallar S" first="Stefania" last="Cavallar">Stefania Cavallar</name>
</author>
<author><name sortKey="Dodson, Bruce" sort="Dodson, Bruce" uniqKey="Dodson B" first="Bruce" last="Dodson">Bruce Dodson</name>
</author>
<author><name sortKey="Lenstra, Arjen" sort="Lenstra, Arjen" uniqKey="Lenstra A" first="Arjen" last="Lenstra">Arjen Lenstra</name>
</author>
<author><name sortKey="Leyland, Paul" sort="Leyland, Paul" uniqKey="Leyland P" first="Paul" last="Leyland">Paul Leyland</name>
</author>
<author><name sortKey="Lioen, Walter" sort="Lioen, Walter" uniqKey="Lioen W" first="Walter" last="Lioen">Walter Lioen</name>
</author>
<author><name sortKey="Montgomery, Peter L" sort="Montgomery, Peter L" uniqKey="Montgomery P" first="Peter L." last="Montgomery">Peter L. Montgomery</name>
</author>
<author><name sortKey="Murphy, Brian" sort="Murphy, Brian" uniqKey="Murphy B" first="Brian" last="Murphy">Brian Murphy</name>
</author>
<author><name sortKey="Te Riele, Herman" sort="Te Riele, Herman" uniqKey="Te Riele H" first="Herman" last="Te Riele">Herman Te Riele</name>
</author>
<author><name sortKey="Zimmermann, Paul" sort="Zimmermann, Paul" uniqKey="Zimmermann P" first="Paul" last="Zimmermann">Paul Zimmermann</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:B4A2079E6539944CEB1347B1ADB16FADDBCE4758</idno>
<date when="1999" year="1999">1999</date>
<idno type="doi">10.1007/978-3-540-48000-6_16</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-36VVVKXJ-J/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002A76</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002A76</idno>
<idno type="wicri:Area/Istex/Curation">002A39</idno>
<idno type="wicri:Area/Istex/Checkpoint">002385</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002385</idno>
<idno type="wicri:doubleKey">0302-9743:1999:Cavallar S:factorization:of:rsa</idno>
<idno type="wicri:Area/Main/Merge">00B051</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:00-0001758</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A81</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000001</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000A86</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A86</idno>
<idno type="wicri:doubleKey">0302-9743:1999:Cavallar S:factorization:of:rsa</idno>
<idno type="wicri:Area/Main/Merge">00B174</idno>
<idno type="wicri:Area/Main/Curation">00A999</idno>
<idno type="wicri:Area/Main/Exploration">00A999</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Factorization of RSA-140 Using the Number Field Sieve</title>
<author><name sortKey="Cavallar, Stefania" sort="Cavallar, Stefania" uniqKey="Cavallar S" first="Stefania" last="Cavallar">Stefania Cavallar</name>
<affiliation wicri:level="3"><country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>CWI, P.O. Box 94079, 1090 GB, Amsterdam</wicri:regionArea>
<placeName><settlement type="city">Amsterdam</settlement>
<region nuts="2" type="province">Hollande-Septentrionale</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Dodson, Bruce" sort="Dodson, Bruce" uniqKey="Dodson B" first="Bruce" last="Dodson">Bruce Dodson</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Lehigh University, Bethlehem, PA</wicri:regionArea>
<placeName><region type="state">Pennsylvanie</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Lenstra, Arjen" sort="Lenstra, Arjen" uniqKey="Lenstra A" first="Arjen" last="Lenstra">Arjen Lenstra</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Citibank, Parsippany, NJ</wicri:regionArea>
<placeName><region type="state">New Jersey</region>
</placeName>
</affiliation>
<affiliation></affiliation>
</author>
<author><name sortKey="Leyland, Paul" sort="Leyland, Paul" uniqKey="Leyland P" first="Paul" last="Leyland">Paul Leyland</name>
<affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Microsoft Research Ltd., Cambridge</wicri:regionArea>
<wicri:noRegion>Cambridge</wicri:noRegion>
</affiliation>
<affiliation></affiliation>
</author>
<author><name sortKey="Lioen, Walter" sort="Lioen, Walter" uniqKey="Lioen W" first="Walter" last="Lioen">Walter Lioen</name>
<affiliation wicri:level="3"><country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>CWI, P.O. Box 94079, 1090 GB, Amsterdam</wicri:regionArea>
<placeName><settlement type="city">Amsterdam</settlement>
<region nuts="2" type="province">Hollande-Septentrionale</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Montgomery, Peter L" sort="Montgomery, Peter L" uniqKey="Montgomery P" first="Peter L." last="Montgomery">Peter L. Montgomery</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Microsoft Research and CWI, 780 Las Colindas Road, 94903-2346, San Rafael, CA</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Murphy, Brian" sort="Murphy, Brian" uniqKey="Murphy B" first="Brian" last="Murphy">Brian Murphy</name>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Computer Sciences Laboratory, The Australian National University, ACT 0200, Canberra</wicri:regionArea>
<wicri:noRegion>Canberra</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Te Riele, Herman" sort="Te Riele, Herman" uniqKey="Te Riele H" first="Herman" last="Te Riele">Herman Te Riele</name>
<affiliation wicri:level="3"><country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>CWI, P.O. Box 94079, 1090 GB, Amsterdam</wicri:regionArea>
<placeName><settlement type="city">Amsterdam</settlement>
<region nuts="2" type="province">Hollande-Septentrionale</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Zimmermann, Paul" sort="Zimmermann, Paul" uniqKey="Zimmermann P" first="Paul" last="Zimmermann">Paul Zimmermann</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>Inria Lorraine and Loria, Nancy</wicri:regionArea>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computation time</term>
<term>Cryptography</term>
<term>Encryption</term>
<term>Factorization</term>
<term>Implementation</term>
<term>Internet</term>
<term>Number theory</term>
<term>Polynomial method</term>
<term>Selection problem</term>
<term>World wide web</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Cryptage</term>
<term>Cryptographie</term>
<term>Factorisation</term>
<term>Implémentation</term>
<term>Internet</term>
<term>Méthode polynomiale</term>
<term>Problème sélection</term>
<term>RSA-140</term>
<term>Réseau WWW</term>
<term>Temps calcul</term>
<term>Théorie nombre</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper. The implications of the new polynomial selection method for factoring a 512-bit RSA modulus are discussed and it is concluded that 512-bit (= 155-digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Pays-Bas</li>
<li>Royaume-Uni</li>
<li>États-Unis</li>
</country>
<region><li>Californie</li>
<li>Grand Est</li>
<li>Hollande-Septentrionale</li>
<li>Lorraine (région)</li>
<li>New Jersey</li>
<li>Pennsylvanie</li>
</region>
<settlement><li>Amsterdam</li>
<li>Nancy</li>
</settlement>
</list>
<tree><country name="Pays-Bas"><region name="Hollande-Septentrionale"><name sortKey="Cavallar, Stefania" sort="Cavallar, Stefania" uniqKey="Cavallar S" first="Stefania" last="Cavallar">Stefania Cavallar</name>
</region>
<name sortKey="Cavallar, Stefania" sort="Cavallar, Stefania" uniqKey="Cavallar S" first="Stefania" last="Cavallar">Stefania Cavallar</name>
<name sortKey="Lioen, Walter" sort="Lioen, Walter" uniqKey="Lioen W" first="Walter" last="Lioen">Walter Lioen</name>
<name sortKey="Lioen, Walter" sort="Lioen, Walter" uniqKey="Lioen W" first="Walter" last="Lioen">Walter Lioen</name>
<name sortKey="Montgomery, Peter L" sort="Montgomery, Peter L" uniqKey="Montgomery P" first="Peter L." last="Montgomery">Peter L. Montgomery</name>
<name sortKey="Te Riele, Herman" sort="Te Riele, Herman" uniqKey="Te Riele H" first="Herman" last="Te Riele">Herman Te Riele</name>
<name sortKey="Te Riele, Herman" sort="Te Riele, Herman" uniqKey="Te Riele H" first="Herman" last="Te Riele">Herman Te Riele</name>
</country>
<country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Dodson, Bruce" sort="Dodson, Bruce" uniqKey="Dodson B" first="Bruce" last="Dodson">Bruce Dodson</name>
</region>
<name sortKey="Dodson, Bruce" sort="Dodson, Bruce" uniqKey="Dodson B" first="Bruce" last="Dodson">Bruce Dodson</name>
<name sortKey="Lenstra, Arjen" sort="Lenstra, Arjen" uniqKey="Lenstra A" first="Arjen" last="Lenstra">Arjen Lenstra</name>
<name sortKey="Montgomery, Peter L" sort="Montgomery, Peter L" uniqKey="Montgomery P" first="Peter L." last="Montgomery">Peter L. Montgomery</name>
</country>
<country name="Royaume-Uni"><noRegion><name sortKey="Leyland, Paul" sort="Leyland, Paul" uniqKey="Leyland P" first="Paul" last="Leyland">Paul Leyland</name>
</noRegion>
</country>
<country name="Australie"><noRegion><name sortKey="Murphy, Brian" sort="Murphy, Brian" uniqKey="Murphy B" first="Brian" last="Murphy">Brian Murphy</name>
</noRegion>
<name sortKey="Murphy, Brian" sort="Murphy, Brian" uniqKey="Murphy B" first="Brian" last="Murphy">Brian Murphy</name>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Zimmermann, Paul" sort="Zimmermann, Paul" uniqKey="Zimmermann P" first="Paul" last="Zimmermann">Paul Zimmermann</name>
</region>
<name sortKey="Zimmermann, Paul" sort="Zimmermann, Paul" uniqKey="Zimmermann P" first="Paul" last="Zimmermann">Paul Zimmermann</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00A999 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00A999 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:B4A2079E6539944CEB1347B1ADB16FADDBCE4758
   |texte=   Factorization of RSA-140 Using the Number Field Sieve
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Factorization of RSA-140 Using the Number Field Sieve

Factorization of RSA-140 Using the Number Field Sieve

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.